package com.yww.datastructure.priorityqueue;

import com.yww.datastructure.queue.Queue;

import java.util.Arrays;
import java.util.Iterator;

/**
 * @author yww
 * @description 使用大顶堆完成优先队列
 * @since 2024/2/6 10:22
 */
@SuppressWarnings("unchecked")
public final class PriorityQueue3<E extends Priority> implements Queue<E> {
    private Priority[] array;
    private int size;

    public PriorityQueue3(int capacity) {
        this.array = new Priority[capacity];
    }

    /**
     * 1. 入堆新元素，加入到数组末尾（索引位置 child）
     * 2. 不断比较新加元素与它父节点（parent）优先级
     * - 如果父节点优先级低，则向下移动，并找到下一个 parent
     * - 直到父节点优先级更高或 child==0 为止
     **/
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int child = size;
        int parent = (child - 1) / 2;
        while (child > 0 && array[parent].priority() < value.priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = value;
        size++;
        return true;
    }

    /**
     * 出队元素
     * 1. 交换堆顶和尾部元素，让尾部元素出队
     * 2. 下潜
     * - 从堆顶开始，将父元素与两个孩子较大者交换
     * - 直到父元素大于两个孩子，或没有孩子为为止
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        // 交换堆顶和尾
        swap(array, 0, size - 1);
        size--;
        Priority tail = array[size];
        array[size] = null; // help gc

        // 下潜
        down(0);
        return (E) tail;
    }

    private void down(int parent) {
        if (parent >= size) {
            return;
        }
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;

        if (left < size && array[max].priority() < array[left].priority()) {
            max = left;
        }

        if (right < size && array[max].priority() < array[right].priority()) {
            max = right;
        }
        if (max != parent) {
            swap(array, parent, max);
            down(max);
        }
    }

    private static void swap(Priority[] arr, int i, int j) {
        Priority temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        int tempSize = size;
        Priority[] tempArray = Arrays.copyOf(array, array.length);
        return new Iterator<E>() {
            @Override
            public boolean hasNext() {
                if (isEmpty()) {
                    array = tempArray;
                    size = tempSize;
                    return false;
                }
                return true;
            }

            @Override
            public E next() {
                return poll();
            }
        };
    }
}
